package com.atguigui.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 30.串联所有单词的子串
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/6/23 10:08
 */
public class P30SubstringWithConcatenationOfAllWords {
    public static void main(String[] args) {
        Solution solution = new P30SubstringWithConcatenationOfAllWords().new Solution();

        String s = "ling mind rabo o fooowingdingbarrwingmonkeypoundcake";
        String[] words = {"fooo", "barr", "wing", "ding", "wing"};

        solution.findSubstring(s, words);

    }

    class Solution {
        /**
         * 做一个滑动窗口
         *
         * @param s     字符串的总长度 = (words[0].length * n)
         * @param words 单词组，每个单词组的长度相同
         * @return
         */
        public List<Integer> findSubstring(String s, String[] words) {
            // 返回结果
            List<Integer> result = new ArrayList<>();
            // 单词长度
            int wordLength = words[0].length();
            // 单词个数
            int wordNums = words.length;

            // 将所有单词放入map，后续可以判断是否匹配
            Map<String, Integer> map = new HashMap<>();
            for (String word : words) {
                if (map.containsKey(word)) {
                    Integer integer = map.get(word);
                    map.put(word, ++integer);
                } else {
                    map.put(word, 1);
                }
            }

            // 开窗 左侧
            int l = 0;
            // 开窗 右侧
            int r = wordLength * wordNums;

            // 开窗寻找
            while (r <= s.length()) {
                Map<String, Integer> newMap = new HashMap<>();
                //复制map
                newMap.putAll(map);
                // 开窗大小
                String str = s.substring(l, r);
                // 一个个单词获取
                for (int i = 0; i < wordNums; i++) {
                    // 获取窗口中每个单词
                    String word = str.substring(i * wordLength, (i + 1) * wordLength);
                    // 判断是否存在words中
                    if (newMap.containsKey(word)) {
                        Integer integer = newMap.get(word);
                        if (integer > 0) {
                            integer--;
                            if (integer == 0) {
                                newMap.remove(word);
                            } else {
                                newMap.put(word, integer);
                            }
                        } else {
                            newMap.remove(word);
                            break;
                        }
                    } else {
                        break;
                    }
                }
                // newMap正好为空则匹配正确
                if (newMap.size() == 0) {
                    result.add(l);
                }
                // 窗口左移一位
                l += 1;
                r += 1;
            }

            return result;
        }
    }
}
